Yesterday we talked about game playing or, as we say in a slightly more scientific way,

adversarial search.

We do search-based problem solving, but there's an adversary in the room.

Last week we learned about minimax search, and here we actually improve on this very

basic idea of minimax search.

What comes out is alpha beta search.

The idea is relatively simple.

The idea is that we can actually snip off certain areas of the search space, and it

turns out that we can snip off in the overall effect an exponential part of the exponential

search space.

What stays over is still exponential, but in D over 2 instead of in D. D is the critical

depth of the solution, is the critical factor, so that actually gives us double the look

ahead.

The idea was that if Max knows that he can always achieve an N, because min, after looking

at the min subtree here, cannot force less than N, then further down the tree, when you

already see I have an M here, which is smaller than N, I do not have to look at this.

Because we're again under min, and we know that here min can't force less than N, so

we don't have to look at the small values here.

Anything under this max tree here.

So the idea here is that we can save a little bit here, and if we are in a good situation,

we can essentially make every second layer of the tree to be choiceless, which gives

us this depth over 2 things.

So we looked at the examples in detail, and the idea of alpha pruning is that next to

the value, which you always compute, you also hold on to the so-called alpha value, which

is really something that actually is going to be transferred into the other branches.

Here the alpha value of 3 is transferred even though the value that kind of looks below

is completely indetermined and therefore plus on infinity here.

And once you see something that's smaller than 3, you can get rid of all the others.

So we looked at the algorithm, and I fixed the typo, and essentially run the algorithm

with the pruning both for max as well as for min.

We get a nice speed up here.

At least one of these things here is choiceless.

Choicelessness we always get if we have ordered the nodes correctly.

If they have the smallest first in here under the min choices, which is kind of the best

for max, then we can throw lots of stuff away.

Here we have ordered the nodes in the wrong order, and there we basically have to look

at all of them.

Still we're small enough to throw the rest away, but here the last one is small enough

so we can't throw away anything.

That was the situation here why we're not getting a speed up here.

We looked at another example where we kind of had an uneven game length, and we can see

that even in this case here we're getting pruning opportunities and speed ups.

Okay, yes?

I have a question to the tree.

For the middle branch, don't we still have to look at every node to know that the first

one is the smallest?

That's not the mechanism.

The mechanism is that this value 2 here, which is smaller than the alpha value of 3, is actually

obtained by this one already.

Even if we would have a 1 in a different branch, it wouldn't matter?